package th.retrofit.lib;

import java.util.ArrayList;
import java.util.List;

/**
 * 匈牙利算法
 */
public class HungarianAlgorithm {

    /**
     * 素数伴侣
     * https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e?tpId=37&&tqId=21251&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
     * @param arr 整数数组，长度为偶数
     * @return 伴侣数量
     */
    public int primePartner(int[] arr) {
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for (int j : arr) {
            if ((j & 1) == 1) {
                odd.add(j);
            } else {
                even.add(j);
            }
        }
        int[] evensMatch =new int[even.size()];
        int result = 0;
        for(int i = 0; i < odd.size(); i++) {
            boolean[] used = new boolean[even.size()];
            if(find(odd.get(i), even, used, evensMatch)) {
                result++;
            }
        }
        return result;
    }

    private boolean find(int x, List<Integer> even, boolean[] used, int[] evensMatch) {
        int eLen = even.size();
        for (int i = 0; i < eLen; i++) {
            if (!used[i] && isPrime(x + even.get(i))) {
                used[i] = true;
                if (evensMatch[i] ==0 || find(evensMatch[i], even, used, evensMatch)) {
                    evensMatch[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i * i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 6, 13};
        System.out.println(new HungarianAlgorithm().primePartner(arr));
    }
}
